package com.gorkr.offer.stackQueueHeap;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author gorkr
 * @date 2022/04/09 19:01
 *
 * java 的 stack 和 queue 的操作
 * Java中用来表达栈的功能（push/pop/peek），更适用的是使用双端队列接口Deque，
 * 并用实现类ArrayDeque/LinkedList来进行初始化。
 * Deque<Integer> stack = new LinkedList<>();
 * 增：deque.offerFirst()， deque.offerLast();//从头添加和尾部添加
 * 删：deque.pollFirst()， deque.pollLast()//从头添加和尾部出队
 * 查：deque.peekFirst(), deque.peekLast()//查看头添加和尾部元素
 * stack : push pop
 * queue : offer poll
 **/
public class OfferMedia31 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 入栈位置
        int flag = -1;

        LinkedList<Integer> stack = new LinkedList<>();

        // 记录压入元素在数组的下标
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < pushed.length; i++) {
            map.put(pushed[i],i);
        }

        for (int i = 0; i <popped.length; i++) {
            Integer index = map.get(popped[i]);
            if(index>flag){
                for (int j = flag+1; j <=index; j++) {
                    stack.push(pushed[j]);
                }
                flag=index;
                stack.pop();
            }else {
                if(!stack.pop().equals(pushed[index])){
                    return false;
                }
            }
        }

        return true;
    }

    @Test
    public void test(){
        int[] pushed = {1,2,3,4,5};
        int[] poped = {4,5,3,2,1};
        System.out.println(validateStackSequences(pushed, poped));
    }
}
    